package tulingxueyuan117;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/5 21:33
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 */
public class p28_对称二叉树_101 {
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(3);
        root1.left = node2;
        root1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        boolean res = isSymmetric(root1);
        System.out.println(res);
    }
//    递归
//    public static boolean isSymmetric(TreeNode root) {
//        if(root==null) return true;
////        调用递归函数，比较左右节点
//        return deepCheck(root.left, root.right);
//    }
//    public static boolean deepCheck(TreeNode left, TreeNode right){
////        递归的终止条件是两个节点都为空
////        或者两个节点中有一个为空
////        或者两个节点值不相等
//        if(left==null && right==null){
//            return true;
//        }
//        if(left==null || right==null){
//            return false;
//        }
//        if(left.val!=right.val){
//            return false;
//        }
////        再递归的比较左孩子的做孩子和右孩子的右节点以及左孩子的右节点和右孩子的左节点
//        return deepCheck(left.left, right.right) && deepCheck(left.right, right.left);
//    }
//    队列和循环迭代
    public static boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode u = root.left;
        TreeNode v= root.right;
        if(root==null || (u==null&&v==null)) return true;
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()){
            u = q.poll();
            v = q.poll();
            if(u==null && v==null){
                continue;
            }
            if((u==null||v==null) || (u.val!=v.val)){
                return false;
            }
            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}
